package cn.kingshion.search;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 二分查找的两种实现方法
 * 方法一是jdk的源码实现
 * 方法二是用递归写的
 */
public class BinarySearchDemo {
    public static void main(String[] args) {
        int[] arr = {-17, 159, 56, 15, 152, 6, 56, 6, 6, 6, 6, 963, 1, 2565, 2, 6, 5151, 62, 2, 15, 98};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
        int index = binarySearch1(arr, 0, arr.length, 6);
        System.out.println("普通版：" + index);

        List<Integer> resIndex = binarySearch2(arr, 0, arr.length, 6);
        System.out.println("增强版：" + resIndex.toString());
    }

    /**
     * 方法一：
     * 移位法
     *
     * @param arr
     * @param fromIndex
     * @param toIndex
     * @param key
     * @return
     */
    public static int binarySearch(int[] arr, int fromIndex, int toIndex, int key) {
        int low = fromIndex;
        int high = toIndex - 1;

        while (low <= high) {
            int mid = (low + high) >>> 1;
            int midVal = arr[mid];

            if (midVal < key)
                low = mid + 1;
            else if (midVal > key)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found.
    }

    /**
     * 方法二：
     * 递归法
     *
     * @param arr
     * @param fromIndex
     * @param toIndex
     * @param key
     * @return
     */
    public static int binarySearch1(int[] arr, int fromIndex, int toIndex, int key) {
        if (fromIndex > toIndex) {
            return -1;
        }
        int mid = (fromIndex + toIndex) / 2;
        int midVal = arr[mid];

        if (midVal < key) {
            return binarySearch1(arr, mid + 1, toIndex, key);
        } else if (midVal > key) {
            return binarySearch1(arr, fromIndex, mid - 1, key);
        } else {
            return mid;
        }
    }

    /**
     * 增强版的二分查找，可以查找到数组中的多个相同的 key 值的 index
     *
     * @param arr
     * @param fromIndex
     * @param toIndex
     * @param key
     * @return
     */
    public static List<Integer> binarySearch2(int[] arr, int fromIndex, int toIndex, int key) {
        if (fromIndex > toIndex) {
            return new ArrayList();
        }
        int mid = (fromIndex + toIndex) / 2;
        int midVal = arr[mid];

        if (midVal < key) {
            return binarySearch2(arr, mid + 1, toIndex, key);
        } else if (midVal > key) {
            return binarySearch2(arr, fromIndex, mid - 1, key);
        } else {
            List<Integer> res = new ArrayList<Integer>();
            int temp = mid - 1;
            while (arr[temp] == key && temp > 0) {
                res.add(temp);
                temp -= 1;
            }
            res.add(mid);
            temp = mid + 1;
            while (arr[temp] == key && temp < arr.length) {
                res.add(temp);
                temp += 1;
            }
            return res;
        }
    }


}
